package org.bb.arithmetic;

import java.util.Arrays;
import java.util.Scanner;

public class SearchTools {
	// 属性
	Scanner sc = new Scanner(System.in);

	/**
	 * 二分查找算法
	 * 
	 * @param arr0
	 *            被查找的数组
	 * @param val0
	 *            被查找的数值
	 * @return 查找到的位置【-1表示没有找到】
	 */
	public int binarySearch(int[] arr0, int val0) {
		// 默认查找位置
		int index = -1;
		// 调用二分查找的递归算法
		if (arr0 != null && arr0.length > 0) {
			// 二分查找的数组需要先进行排序
			Arrays.sort(arr0);
			index = doBinarySearch(arr0, val0, 0, arr0.length - 1);
		}
		return index;
	}

	/**
	 * 二分查找算法【被递归调用的方法】
	 * 
	 * @param arr0
	 *            被查找的数组
	 * @param val0
	 *            被查找的值
	 * @param low
	 *            查找的起始位置
	 * @param high
	 *            查找的结束位置
	 * @return 查找结果【-1表示没有找到】
	 */
	private int doBinarySearch(int[] arr0, int val0, int low, int high) {
		// 结束条件
		if (low >= high) {
			// 结束，没有找到
			return -1;
		}
		// 计算中间位置
		int mid = (low + high) / 2;
		// 根据和中间位置比较的进行递归调用
		// 找到，结束
		if (val0 == arr0[mid]) {
			return mid;
		} else if (val0 > arr0[mid]) {
			// 在后半截找
			// 后半截的起始下标变为 mid+1
			int lowNew = mid + 1;
			// 后边截的结束下标不变，还是high
			// 递归调用
			return doBinarySearch(arr0, val0, lowNew, high);
		} else {
			// 在前半截找
			// 前半截的结束下标变为 mid-1
			int highNew = mid - 1;
			// 前边截的开始下标不变，还是low
			// 递归调用
			return doBinarySearch(arr0, val0, low, highNew);
		}

	}

	/**
	 * 普通查找算法[等值匹配]
	 * 
	 * @param arr0
	 *            被查找的数组
	 * @param val0
	 *            查找的值
	 * @return 查找的位置【-1表示没有找到】
	 */

	public int nomalSearch(int[] arr0, int val0) {
		// 默认查找位置
		int index = -1;
		// 查找个数是否在数组中
		if (arr0 != null && arr0.length > 0) {
			// 使用等值匹配查找该数是否在数组，并输出所在的位置
			for (int i = 0; i < arr0.length; i++) {
				// 等值查找
				if (arr0[i] == val0) {
					// 找到，输出，退出
					index = i;
					break;
				}
			}
		}
		// 返回查找的位置
		return index;
	}

	/**
	 * 从控制台获取一个整型的数
	 * 
	 * @return 获取的数
	 */
	public int getVal() {
		// 输入一个整型的数
		System.out.println("请输入要查找一个整型的数：");
		int val0 = sc.nextInt();
		return val0;
	}

	/**
	 * 获取一个初始化数组
	 * 
	 * @return 数组
	 */
	public int[] initArr() {
		// 输入数组的长度

		System.out.println("请输入数组的长度：");
		int len = sc.nextInt();
		// 创建初始化数组
		int[] arr = new int[len];
		for (int i = 0; i < arr.length; i++) {
			System.out.println("请输入数组的第" + i + "个元素：");
			int val = sc.nextInt();
			arr[i] = val;
		}
		// 输出初始化的数组
		printArr(arr);
		return arr;
	}

	/**
	 * 打印数组内容
	 * 
	 * @param arr
	 *            被打印的数组
	 */
	public void printArr(int[] arr) {
		System.out.println("数组内容为：");
		for (int i : arr) {
			System.out.print(" " + i);
		}
		// 换行
		System.out.println();
	}
}
